#
# @lc app=leetcode.cn id=17 lang=python3
#
# [17] 电话号码的字母组合
#
# https://leetcode-cn.com/problems/letter-combinations-of-a-phone-number/description/
#
# algorithms
# Medium (57.60%)
# Likes:    1705
# Dislikes: 0
# Total Accepted:    405K
# Total Submissions: 702.5K
# Testcase Example:  '"23"'
#
# 给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。
# 
# 给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
# 
# 
# 
# 
# 
# 示例 1：
# 
# 
# 输入：digits = "23"
# 输出：["ad","ae","af","bd","be","bf","cd","ce","cf"]
# 
# 
# 示例 2：
# 
# 
# 输入：digits = ""
# 输出：[]
# 
# 
# 示例 3：
# 
# 
# 输入：digits = "2"
# 输出：["a","b","c"]
# 
# 
# 
# 
# 提示：
# 
# 
# 0 <= digits.length <= 4
# digits[i] 是范围 ['2', '9'] 的一个数字。
# 
# 
#
# %%
from typing import List
# @lc code=start
class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        all_combin = []
        letters = "abcdefghijklmnopqrtuvwxy"
        mapping = {str(key+2):letters[3 * key:3 * key+3] for key in range(8)}
        mapping['7'] += 's'
        mapping['9'] += 'z'
        if not digits:
            # is None
            return []
        if mapping.get(digits):
            return [i for i in mapping.get(digits)]
        else:
            # not one
            for ch in mapping[digits[0]]:
                all_combin.extend([ch + i for i in self.letterCombinations(digits[1:])])
            return all_combin
# @lc code=end

# %%
s = Solution()
s.letterCombinations("23")